/**
 * 最接近的三数之和
 *
 * 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
 * 返回这三个数的和。
 * 假定每组输入只存在恰好一个解。
 *
 * 示例 1：
 * 输入：nums = [-1,2,1,-4], target = 1
 * 输出：2
 * 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2)。
 *
 * 示例 2：
 * 输入：nums = [0,0,0], target = 1
 * 输出：0
 * 解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。
 *
 * 提示：
 * 3 <= nums.length <= 1000
 * -1000 <= nums[i] <= 1000
 * -104 <= target <= 104
 */

import java.util.Arrays;

/**
 * 这题的思路和上题的三数之和一样, 先固定一个数, 再寻找另两个数相加的和与之前的数的和谁离 target 最近
 * 但着题要简单一点, 这题不存在重复出现的数, 因为题目明确了有唯一的解
 * 但又一点比上一题要难, 就是这题需要求谁离的最近, 这就有两种可能性了, 一种是和在他的左边离他最近, 另一种是和在右边离他最近
 * 这里我们可以比较两者之差, 看看谁最小, 就把这时的总和记录下来
 * 做着个算法时, 我们要注意一定要拿大的数减去小的数, 这样才能保证比较的是他们之间的距离
 */

public class Main {
    public int threeSumClosest(int[] nums, int target) {

        // 求得他们的长度
        int n = nums.length;

        // 特判一下, 要是长度为三, 直接返回他们三个的总和
        if (n == 3) {
            return nums[0] + nums[1] + nums[2];
        }

        // 将数组排序
        Arrays.sort(nums);

        // 定义比较最小的距离
        int ret = Integer.MAX_VALUE;

        // 最终返回的结果
        int result = 0;

        // 从后向前遍历, 这样处理另两个数的时候不容易越界
        for (int i = n - 1; i > 1; i--) {

            // 定义另外两个数
            int left = 0, right = i - 1;

            // 出循环条件依然是两者相遇
            while (left < right) {

                // 求出三者总和
                int sum = nums[left] + nums[right] + nums[i];

                // 比较与target的大小
                if (sum < target) {

                    // 小了向左边找, 要是差小于之前的差, 记录此次的总和
                    left++;
                    if (target - sum <= ret) {
                        ret = target - sum;
                        result = sum;
                    }
                } else if (sum > target) {

                    // 大了向右边找, 要是差小于之前的差, 记录此次的总和
                    right--;
                    if (sum - target <= ret) {
                        ret = sum - target;
                        result = sum;
                    }
                } else {

                    // 要是直接相等了, 这时一定是最小的, 返回 target
                    return target;
                }
            }
        }

        // 返回结果
        return result;
    }
}